Computers with dataflow architectures, known-as "dataflow machines", are known in the art. They are described in an overview article by David E. Culler and Arvind, "Dataflow Architecture," Annual Reviews in Computer Science, 1986. The article is incorporated herein by reference.
Briefly, the dataflow model of computation describes a program by a directed graph, shown in FIG. B-1 to which reference is now made, where nodes 10-13 denote instructions of any type, and arcs 14 denote data dependencies. The term "instruction" refers to the operation performed at a node.
The function graphed by the dataflow graph of FIG. B-1 is: EQU H=[(C+D)*(E-F)]/F (1)
In the dataflow model, the data values A-H are carried as "tokens" along the arcs 14 and a node 10-13 can execute whenever its input data, or operands, are available. Thus, in the example shown in FIG. B-1, nodes 10 and 11 can execute independently of the other nodes and of each other, node 12 must wait until both of nodes 10 and 11 have executed, and node 13 must wait until node 12 has executed.
In the ideal dataflow model, each arc 14 is an unlimited first-in-first-out (FIFO) buffer and each node operates on its operands in a FIFO manner. This, however, is not a practical model. Typically, one or the other or both of the requirements of FIFO operation have to be relaxed.
For example, the requirement of FIFO operation at the nodes might be relaxed. If so, then the operands must be "tagged" in some way. The operands which are provided to an instruction which executes more than once, such as an instruction within a loop or within a subroutine, must belong to the same iteration number and/or the same invocation of the subroutine.
Therefore, in some, "dynamic" dataflow architectures, the operands are tagged to indicate to which performance, or "instantiation", of the instruction they belong. The given instruction, being the one about to execute, then has to search among the tokens on its arcs 14 to find two operands with similar tags to serve as its input for the current instantiation.
It will be noted that the model described herein of the dataflow machine assumes that at most two operands are needed for each instruction.
An example architecture for a dynamic tagged dataflow machine is shown in FIG. B-2. It has an input unit 20, for forwarding, one at a time, operands received either from the outside or from an output unit 22 to a matching store unit 24.
When a tagged operand enters the matching store 24, its tag is compared to the tags of all the other operands stored therein. If the tag of the entering operand matches a tag of one of the stored operands, then the entering operand and the operand which is matched to it are forwarded to an instruction fetch unit 26 and the matched operand is purged from the matching store 24.
Otherwise, the entering operand is stored in the matching store 24 to await its matching operand.
The instruction fetch unit 26 receives the pair of operands and from the information stored in their tags, fetches the instruction to which they belong from a program and data memory 25. The unit 26 then queues the instruction and its operands for eventual execution by an execution unit 28.
The execution unit 28 executes the instruction and produces a result. The result is combined with an appropriate tag and provided to the output unit 22, for returning the result to the input unit 20 as a newly available operand.
It will be noted that the machine of FIG. B-2 is operative for scalar operations only.
Other forms of dataflow architectures are discussed in the paper by Culler and Arvind, described hereinabove.
The dataflow architecture described hereinabove in FIG. B-2 provides instructions to the execution unit 28 whenever the two operands are available for an instruction. Successive executed instructions typically are not related to each other and thus, the output of a first instruction is, in general, not used as an input to a second succeeding instruction.
If we define a critical path through a program as being the longest set of consecutive instructions which cannot be avoided and if we define a data dependence path as a path in which the next instruction depends on the output of the previous instruction, then the executed instructions of prior art dataflow machines do not follow data dependence paths and therefore, do not follow the critical path.
Furthermore, prior art dataflow machines require mechanisms to tag and store every result produced by the execution unit 28. The overhead of this mechanism applied over the entirety of results of a program results in a very slow memory access cycle.
There also exist dataflow/Von-Neumann hybrid machines. These are designed to overcome the long pipeline which is characteristic of pure dataflow machines. Specifically, they try to improve the matching store unit 24 and the "compute address of next instruction" operation performed by the execution unit 28. The following articles describe some of the proposed solutions:
Bic L., "A Process Oriented Model for Efficient Execution of Dataflow Programs", Proceedings of the 7th International Conference on Distributed Computing, Berlin, W. Germany, September 1987; and
Iannucci R., A dataflow/von-Neumann Hybrid, LCS TR-418, MIT, Cambridge, Mass., May 1988.
The dataflow/Von-Neumann hybrids described in the above-mentioned articles use compilers which pre-package the machine code of the program into sequences which can only execute in order. The hybrids benefit from this restriction by not having to compute at run-time the address of the next instruction in the sequence, since the compiler has already fixed the only way to go. The apriori assumption about the exact sequence of execution also avoids the need to check for availability of operands in some cases because the compiler fixes their time of execution and their location in memory.
However, it is, in general, difficult to know at compile time how a program will develop dynamically and therefore, the dataflow/Von-Neumann hybrids cannot fully exploit the parallelism available in the program being run.
An article by I. Gottlieb, one of the present Applicants, "Dynamic Structured Data Flow: Preserving the Advantages of Sequential Processing in a Data Driven Environment", International Conference on parallel Processing, Chicago, 1988, is a theoretical discussion of an architectural model for automatic sequencing of parallel operations characteristic of dataflow.